package com.javaDemo.ti;

import java.util.Arrays;

/**
 * 快速排序算法实现
 * 
 * @ClassName: Kuaisupaixu
 * @Auther: csy
 * @Date: 2020/5/18 00:35
 * @Description: 实现了经典的快速排序算法，用于高效排序数组
 * 
 * 算法思想：
 * 1. 快速排序是一种分治策略的排序算法
 * 2. 通过选择基准值(pivot)，将数组分为两部分：小于基准值和大于基准值的元素
 * 3. 递归地对这两部分进行排序，最终得到完全有序的数组
 * 4. 平均时间复杂度为O(nlogn)，最坏情况为O(n²)
 * 
 * 适用场景：
 * 1. 大规模数据排序
 * 2. 对排序速度要求较高的场景
 * 3. 不要求排序的稳定性
 */
public class Kuaisupaixu {
    
    /**
     * 主方法：用于测试快速排序算法
     * 
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        // 测试用例1：普通整数数组
        int[] arr1 = {5, 1, 7, 3, 1, 6, 9, 4};
        System.out.println("测试用例1：");
        System.out.println("排序前：" + Arrays.toString(arr1));
        quickSort(arr1, 0, arr1.length - 1);
        System.out.println("排序后：" + Arrays.toString(arr1));
        
        // 测试用例2：已经有序的数组
        int[] arr2 = {1, 2, 3, 4, 5, 6};
        System.out.println("\n测试用例2：");
        System.out.println("排序前：" + Arrays.toString(arr2));
        quickSort(arr2, 0, arr2.length - 1);
        System.out.println("排序后：" + Arrays.toString(arr2));
        
        // 测试用例3：逆序数组
        int[] arr3 = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        System.out.println("\n测试用例3：");
        System.out.println("排序前：" + Arrays.toString(arr3));
        quickSort(arr3, 0, arr3.length - 1);
        System.out.println("排序后：" + Arrays.toString(arr3));
        
        // 测试用例4：包含重复元素的数组
        int[] arr4 = {3, 3, 3, 3, 3, 3};
        System.out.println("\n测试用例4：");
        System.out.println("排序前：" + Arrays.toString(arr4));
        quickSort(arr4, 0, arr4.length - 1);
        System.out.println("排序后：" + Arrays.toString(arr4));
    }

    /**
     * 快速排序算法实现
     * 
     * 算法步骤：
     * 1. 选择基准值(pivot)：通常选择数组的第一个元素
     * 2. 分区过程：将小于基准值的元素放到左边，大于基准值的元素放到右边
     * 3. 递归排序：对左右两个子数组分别进行递归排序
     * 4. 基线条件：当子数组长度小于等于1时，停止递归
     * 
     * 举例说明：
     * 对数组[5,1,7,3,1,6,9,4]进行排序
     * 1. 选择基准值5
     * 2. 分区后得到[1,1,4,3,5,6,9,7]，基准值5在正确位置
     * 3. 递归排序左子数组[1,1,4,3]和右子数组[6,9,7]
     * 4. 最终得到完全有序的数组[1,1,3,4,5,6,7,9]
     *
     * @param arr        待排序数组
     * @param leftIndex  待排序区间的起始位置
     * @param rightIndex 待排序区间的结束位置
     */
    private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        // 基线条件：如果左索引大于等于右索引，说明区间长度小于等于1，已经有序
        if (leftIndex >= rightIndex) {
            return;
        }
        
        // 保存初始的左右索引，用于后续的递归调用
        int left = leftIndex;
        int right = rightIndex;
        
        // 选择待排序区间的第一个元素作为基准值
        int key = arr[left];
        
        // 从左右两边交替扫描，直到left和right相遇
        while (left < right) {
            // 从右往左扫描，找到第一个比基准值小的元素
            while (left < right && arr[right] >= key) {
                right--;
            }
            // 将找到的元素放入左侧空位
            arr[left] = arr[right];
            
            // 从左往右扫描，找到第一个比基准值大的元素
            while (left < right && arr[left] <= key) {
                left++;
            }
            // 将找到的元素放入右侧空位
            arr[right] = arr[left];
        }
        
        // 将基准值放入最终位置（left和right相等的位置）
        arr[left] = key;
        
        // 递归排序基准值左边的子数组
        quickSort(arr, leftIndex, left - 1);
        
        // 递归排序基准值右边的子数组
        quickSort(arr, right + 1, rightIndex);
    }
}
